import java.util.ArrayList;
import java.util.List;

public class YangHuiTriangle {
    public static void main(String[] args) {
        System.out.println(triangle(10, 2));
        print(100);
    }

    //未优化版杨辉三角
    public static int triangle(int i,int j){
        if (j==0 || i==j){
            return 1;  //一条边，都是1,//斜边，都是1
        }
        return triangle(i-1,j) + triangle(i-1,j-1);
    }


    //未优化打印
    public static void print1(int n){
        for (int i=0;i<n;i++){
            printSpace(n,i);
            for (int j=0;j<=i;j++){
                System.out.printf("%4d",triangle(i,j));
            }
            System.out.println();
        }
    }

    //优化打印杨辉三角
    public static void print(int n){
        int[][] m = new int[n][];
        for (int i=0;i<n;i++){
            m[i] = new int[i+1];
//            printSpace(n,i);
            for (int j=0;j<=i;j++){
                System.out.printf("%4d",triangle1(m,i,j));
            }
            System.out.println();
        }
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0;i<numRows;i++){
            List<Integer> row = new ArrayList<>();
            for (int j=0;j<=i;j++){
                if (j== 0 || j==i ){
                    row.add(1);
                }else {
                    row.add(list.get(i-1).get(j)+list.get(i-1).get(j-1));
                }
            }
        }
        return list;
    }

    //打印空格
    public static void printSpace(int n,int i){
        int num = (n-i-1)*2;
        for (int j=0;j<num;j++){
            System.out.print(" ");
        }
    }


    //优化版
    public static int triangle1(int[][] m,int i,int j){
        if (m[i][j]>0){
            return m[i][j];
        }
        if (j==0 || i==j){
            m[i][j] = 1;
            return 1;  //一条边，都是1,//斜边，都是1
        }
        m[i][j] = triangle1(m,i-1,j) + triangle1(m,i-1,j-1);
        return m[i][j];
    }
}
